package leetcode.code0799;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {
	int poured;

	public double champagneTower(int poured, int query_row, int query_glass) {
		this.poured = poured;
		Double[][] dp = new Double[query_row + 1][query_glass + 1];
		return Math.min(1, this.champagneTower(query_row, query_glass, dp));
	}

	private double champagneTower(int row, int glass, Double[][] dp) {
		if (row == 0 && glass == 0) {
			return this.poured;
		}
		if (dp[row][glass] != null) {
			return dp[row][glass];
		}
		double ans = 0;
		if (glass == 0) {
			ans = this.champagneTower(row - 1, glass, dp);
			ans = Math.max(0d, (ans - 1) / 2);
		} else if (glass == row) {
			ans = this.champagneTower(row - 1, glass - 1, dp);
			ans = Math.max(0d, (ans - 1) / 2);
		} else {
			double ret1 = this.champagneTower(row - 1, glass - 1, dp);
			double ret2 = this.champagneTower(row - 1, glass, dp);
			ans = Math.max(0d, (ret1 - 1) / 2) + Math.max(0, (ret2 - 1) / 2);
		}
		dp[row][glass] = ans;
		return dp[row][glass];
	}

	@Override
	public void debug4() {
		System.out.println(this.champagneTower(100, 6, 0));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
